This invention relates to the design of graphical models for cyber security, and in particular, to a separation and integration approach of graphical models to protect enterprise networks against intruder attacks.
In enterprise networks, the critical importance of network security and information assurance is a major concern. An enterprise network is a network for a large business or enterprise. It may comprise a number of local area networks that have to interface with each other as well as database management systems and many client workstations. The design and management of enterprise networks can be very complex and may include several different types of networks and computer systems from different vendors.
In particular, for network-centric warfare, in order to ensure mission success, the network-centric enterprise needs to have the capability to provide real-time situational awareness and decision assistance so that the information services are reliable, secure, available, and correct. However, it is believed that technology currently available is incapable of achieving such goals.
Generally, securing networks and systems entails three steps: prevention, detection, and action. Many research efforts and products have addressed problems related to prevention (e.g., firewalls) and detection (e.g., Intrusion Detection Systems (IDS)), and the strategies of “compartmentalization” and “defend-in-depth” have been deployed in enterprise networks. However, there is a lack of “action” related systems to effectively deal with enterprise network intrusion.
Products currently available may provide a significant benefit; however, the filters and network/host monitors that are available block traffic and report misbehavior based largely on rules, signatures, and not a situational analysis. For example, with current Intrusion Detection Systems, low-level alarms will be issued, but no high-level situation awareness is provided. Furthermore, although there is some development related to alarm correlation, this focuses mostly on local events in which it is up to the operator to correlate events in the entire network/system level, to evaluate the current network situation, to assess the cyber attack damage, and to maintain the support of various applications and missions. However, the complexity and dynamic nature of the networks and systems that comprise the information enterprise can make it difficult for operators to interpret and manage. Therefore, during cyber attacks, human operators can be inundated by a large number of alarms without being able to correlate, understand, evaluate, or act upon them. Even under normal operations, the operators need to understand the current status of the networks and systems in order to support missions, analyze security risks, and plan for security countermeasures. With the complexity of enterprise networks, this alone is a daunting task even without the need to react to alarms.
The prior art of detecting attacks merely transforms raw data to information (such as alarm). Current systems for transforming information to intelligence (i.e., situational awareness and action planning) are significantly lacking, and useful software tools for such purposes are not currently available.
In general, current attack graphs model cyber-attacks networks and systems, and the questions that can be answered are related to network and system-specific aspects (e.g., host, systems, vulnerabilities and exploits, etc.). Such graphs cannot execute application and mission-level damage assessment. Furthermore, the dependency of applications and missions on underlying networks and systems can naturally be modeled using graphs where the edges represent the “depends-on” relationship. Such dependency graphs have been proposed in literature to analyze applications (e.g., database) and operating system intrusion recovery. However, such models are insufficient to render network-specific security analysis due to their simplistic semantics and limited scalability. In order to provide a full picture for network security assessment, a unified approach is required that can execute both the network-level security analysis and the high-level application and mission assessment.
In order to support security management tasks in enterprise networks (with potentially thousands of devices), the graphic models need to be scalable. This is particularly critical for attack graphs since they need to handle the systems and network devices. Thus, one of the biggest impediments to achieving scalability is state explosion. As such, most available prior art only supports static analysis to answer questions, such as, “Given the current network configurations, which are the weakest spots that need immediate attention?” While static analysis is useful, it is not sufficient if the goal is to achieve real-time situational awareness and responsive action planning.
Attack graphs that provide poor scalability, inefficient analysis, and that require various manual efforts are impractical; however, various kinds of attack graphs have been proposed for analyzing network security. It should be noted that the term “attack graph” is commonly used; however, the definition of an attack graph is not uniform and different uses may associate unique semantics with nodes (endpoints of graphical elements) and edges in models.
One prior art attack graph is described in a publication by Carnegie Mellon University professors. In the Carnegie Mellon attack graph, nodes represent the network state and attributes, such as hosts and services, and the edges represent specific exploits. Each path in the attack graph describes a specific series of attack instances leading to an attack (e.g., gaining root access of some host). The Carnegie Mellon attack graph is rich in semantics, since essentially, it is capable of modeling all aspects of a network state, security attributes, and attack methods. As a result, the scalability of this attack graph is extremely poor, as the possible number of states is exponential. The poor scalability makes overall analysis capability unfeasible except for very small networks. This inhibits the practical use, and due to the scalability problems, tremendous manual efforts are required.
Another prior art attack graph has been developed at George Mason University. The George Mason attack graph aimed to reduce the size of the resulting attack graph by using a layered organization of the attributes and employing an efficient search algorithm. The key assumption in the George Mason attack graph is “monotonic attack,” that is, privileges obtained at prior stages will stay and not be eliminated in subsequent actions. The George Mason attack graph is significantly reduced compared to the Carnegie Mellon attack graph, yet the George Mason attack graph encodes a significant portion of or almost all of the Carnegie Mellon attack graph semantics. However, the scalability of the George Mason attack graph is still less than would be desired for large networks. A computation grows as N6, where N is a number of hosts. Similar to the Carnegie Mellon attack graph, it is believed that this kind of attack graph is not practical for enterprise networks, unless further reduction of the graph size is achieved.
Another attack graph has been developed at Kansas State University. The semantics of the Kansas State attack graph is different from the George Mason and Carnegie Mellon attack graphs. Essentially, nodes represent a lot and edges represent a little. This is in accordance with the rationale based on a reasoning system called MulVAL (also developed by the same authors) for automatically identifying security vulnerabilities in enterprise networks. The key idea is that most configuration information can be represented as Datalog (a syntactic subset of Prolog) tuples (a set of values passed from one programming language to another application program or to a system program such as an operating system), and most attack techniques can be specified using Datalog rules. The logical attack graph can thus be viewed as a derivation graph for successful Datalog logic analysis. The worst case computation complexity grows between O(N2) and O(N3), which is heretofore the best known computation upper bound for nontrivial attack graphs. A major limitation of the Kansas State attack graph is its analysis capability. No automatic analysis algorithm is provided. Furthermore, for every “what-if” question, a new attack graph must be created. The regeneration requirement and lack of inference capability severely limit the Kansas State attack graph usability in enterprise networks.
Other attack graphs have been developed at the MIT Lincoln Laboratory. These include graphs known as a Full Graph, a Host Compromise Graph, and a Predictive Attack Graph. In general, nodes in these graphs represent hosts, and edges represent vulnerabilities. Generally speaking, these attack graphs represent the hosts and how attackers can reach hosts through vulnerabilities. The different kinds of attack graphs show different semantics and capabilities.
The MIT Full Graph shows all possible paths or sequences of compromised hosts and vulnerabilities that an attacker can use to compromise all hosts in the network. Essentially, the number of nodes in the Full Graph and the computation grow as N!. For example, in a subnet with only 10 hosts, the Full Graph could contain more than 3 million nodes, and one additional host increases the graph size and computation requirements by an order of magnitude. Such factorial complexity clearly reduces the scalability of this type of graph, which we believe makes it unsuitable for practical usage in enterprise networks.
The MIT Host Compromise Graph has edges that represent one of possibly many sequences of vulnerabilities that can lead to a compromise. As a result, the Host Compromise Graph encodes the minimum information for determining the security of enterprise networks, that is, what hosts can be compromised and what privileges can be obtained, regardless of the specific sequence of attack steps. It can be demonstrated that the Host Compromise Graph computation is upper bounded as O(N2), without a significant loss of semantics. The Host Compromise Graph finds the host that can be compromised and “one” path to achieve the compromise. Such a “one-shot” analysis can be efficient; however, testing any single hypothesis requires regenerating the entire Host Compromise Graph. Therefore, its analytic capability is restricted, which severely limits its power and practicality as a useful tool in enterprise networks. In other words, the Host Compromise Graph is scalable, but not really practical for enterprise networks.
The semantics of the MIT Predictive Attack Graph lies between the Full Graph and Host Compromise Graph. It captures all possible paths of the attack, but omits duplicate paths in the Full Graph by pruning. Essentially, it models the “attack reachability” of a particular network. The computational requirement is somewhere between O(N2) and O(N3); however, in some cases, a Predictive Attack Graph can become much larger. As such, its scalability is uncertain, though it does offer some promise. As to analysis capability, the Predictive Attack Graph facilitates automatic static analysis in a fairly efficient manner. The Predictive Attack Graph approach is believed to be the only prior art tool practical for enterprise network security management. However, the Predictive Attack Graph does not support real-time situational awareness or answer predictive “what-if” questions, such as, “What will be the impact on security if I do X and Y, given the current evidence of attacks?” For large-scale enterprise networks, and military networks in particular, such situational awareness and dynamic response capability is extremely important.
Based upon the study of the prior art, it is believed that the semantics of an attack graph can pre-determine several characteristics including representation richness, scalability, and analysis capability. For example, the Carnegie Mellon University attack graph captures all aspects of network states and exploits; however, the attack graph size is often prohibitive, and the poor scalability makes it impractical for enterprise networks. At the other end of the spectrum, if an attack graph only captures what hosts can be compromised, such as the MIT Host Compromise Graph, then weak semantics limit the analysis capability. Therefore, it is an object of the invention to provide an attack graph that provides a balance between extremes.
It is another object of the invention to provide an attack graph for security analysis that provides situational awareness and decision support to the operators, who are users of the attack graph tool. As such, it is a further object of the invention that the application requirements from the operators should play a key role in determining the attack graph semantics. The first information that should be obtained from the users is, “What kinds of questions are important and need to be answered by the attack graph tool?”
It should further be appreciated that given the user application requirements, the actual design of the attack graph is limited by the availability of the informational sources. Such informational sources include, for example, network reachability and vulnerability details. Most of the prior art assumes the availability of network reachability information; however, this assumption creates a significant burden on operators who need to provide such information. Accordingly, it is a further object of the invention to provide a useful tool by automatically computing the reachabillity information in a more accurate and efficient manner.
It is also believed that an attack graph that captures all possible sequences of attacks on all aspects of network resources leads to a state explosion and ruins scalability. Therefore, it is an object of the present invention to alleviate the need for full graphing, which inherently includes extensive redundancy embedded in such full graphs. In full graphs, the same sequence of attacks can appear multiple times. Accordingly, it is an additional object of the invention to reduce and compress redundancy while minimizing a loss of semantics power. As such, a further object of the subject invention is to generate attack graphs with rich semantics that exploit a compressed format for better scalability.